/**
 * 只出现一次的数字 2
 *
 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
 * 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
 *
 * 示例 1：
 * 输入：nums = [2,2,3,2]
 * 输出：3
 *
 * 示例 2：
 * 输入：nums = [0,1,0,1,0,1,99]
 * 输出：99
 *
 * 提示：
 * 1 <= nums.length <= 3 * 104
 * -231 <= nums[i] <= 231 - 1
 * nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
 */

/**
 * 这里使用的方法很巧, 你看我们重复的数有 3 个, 那么当我们把他们看作二进制的时候,
 * 同一个位置要是有相同位置的 1 的话, 那么就是最少 3 个, 我们要是将这个 1 全加起来,
 * 然后在 % 3 那么, 最后剩下的 1, 肯定就是单独一个数的 1 了.
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public int singleNumber(int[] nums) {

        // 返回结果
        int res = 0;

        // 遍历 4 * 8 byte = 32 bit
        for (int i = 0; i < 32; i++) {

            // 这个用于记录每个位置的总和
            int sum = 0;

            // 遍历每一个数
            for (int x : nums) {

                // 这里取每个数的 第 i 个位置的值, 因为只取一个值, 所以需要 & 1;
                // 在将这些值相加
                sum += (x >> i) & 1;
            }

            // 因为相同的有三个, 所以 % 3
            sum %= 3;

            // 将这个位置的值恢复到原来的位置, 要 | 上, 因为后面还有数, 为了不影响后面的数
            res |= sum << i;
        }

        // 返回结果
        return res;
    }
}